package leecode.二分法;

import java.util.Arrays;

public class 寻找排序数组目标值的起始和末尾值 {
    public static void main(String[] args) {
        Soulution soulution = new Soulution();
        int[] ints = soulution.searchRange2(new int[]{2,2,2,2,2}, 2);
        System.out.println(Arrays.toString(ints));
    }

    static class Soulution {
        public int[] searchRange(int[] nums, int target) {
            int length = nums.length;
            int left = 0, right = nums.length - 1;
            int[] re = new int[2];
            if (length == 0) {
                re[0] = re[1] = -1;
                return re;
            }
            if (nums[0] == target && length == 1) {
                re[0] = re[1] = 0;
                return re;
            }
            if (nums[0] != target && length == 1) {
                re[0] = re[1] = -1;
                return re;
            }

            if (length <= 999999999) {
                if (nums[0] == nums[right] && nums[0] == target) {
                    re[0] = 0;
                    re[1] = right;
                    return re;
                }

                for (int i = 0; i < length; i++) {

                    if (nums[i] == target) {
                        int z = i;
                        int temp = 0;
                        for (int j = z; j < length; j++) {
                            if (j == length - 1) {
                                temp = j + 1;
                            }
                            if (nums[j] != target) {
                                temp = j;
                                break;
                            }
                        }
                        re[0] = i;
                        re[1] = temp - 1;
                        return re;
                    }


                }
            }
            re[0] = -1;
            re[1] = -1;
            return re;
        }

        public int[] searchRange2(int[] nums, int target) {
            int[] res = {-1, -1};
            if (nums.length == 0) return res;

            int l = 0, r = nums.length - 1;
            // 查找到target之后，给res[0]赋值，继续向左二分查找
            while (r >= l) {
                int mid = (r - l) / 2 + l;
                if (nums[mid] == target) {
                    res[0] = mid;
                    r = mid - 1;
                } else if (nums[mid] > target) r = mid - 1;
                else if (nums[mid] < target) l = mid + 1;
            }
            // 别忘了重置
            l = 0;
            r = nums.length - 1;
            // 查找到target之后，给res[1]赋值，继续向右左二分查找
            while (r >= l) {
                int mid = (r - l) / 2 + l;
                if (nums[mid] == target) {
                    res[1] = mid;
                    l = mid + 1;
                } else if (nums[mid] > target) r = mid - 1;
                else if (nums[mid] < target) l = mid + 1;
            }
            return res;
        }

    }


}
